package exercises.leetcode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * <a href="">
 * </a>
 *
 * <p><span color="#87CEEB">描述:</span>
 *
 * @author or2
 * @date 2021年10月26日 时间: 20:59
 */
public class No301 {
    private int len = 0;

    public List<String> removeInvalidParentheses(String s) {
        char[] s2chars = s.toCharArray();
        int left = 0, right = 0;
        for (char ch : s2chars)
            if      (ch == '(') left++;
            else if (ch == ')') right++;

        int max = Math.min(left, right);
        var all = new HashSet<String>();

        dfs(s2chars, 0, 0, max, "", all);
        var ans = new ArrayList<>(all);
//        for (String str : all)
//            if (str.length() == len) ans.add(str);

        return ans;
    }

    private void dfs(char[] chars, int curIndex, int score, int max, String curS, Set<String> ans) {
        if (curIndex == chars.length) {
            if (score == 0 ) if (curS.length() == len) {
                ans.add(curS);
            } else if (curS.length() > len) {
                len = curS.length();
                ans.clear();
                ans.add(curS);
            }
            return;
        }

        if (chars[curIndex] == '(') {
            if (score + 1 <= max) dfs(chars, curIndex + 1, score + 1, max, curS + "(", ans);
            dfs(chars, curIndex + 1, score, max, curS, ans);
        } else if (chars[curIndex] == ')') {
            if (score > 0) dfs(chars, curIndex + 1, score - 1, max, curS + ")", ans);
            dfs(chars, curIndex + 1, score, max, curS, ans);
        } else
            dfs(chars, curIndex + 1, score, max, curS + chars[curIndex], ans);
    }
}
